class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 自顶而下
class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        # 考虑获取任何一个跟的高度，通过判断跟的高度来进行对比。我能想到的是
        # 自顶而下的递归.这种效率显然地下，因为下面的节点的高度会被计算很多遍
        def height(root):
            if not root:
                return 0
            return max(height(root.left),height(root.right)) + 1
        if not root:    # 无根节点，平衡
            return True
        return abs(height(root.left) - height(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)

# 自底而上。且这种方法可以一旦发现左子树不满足。很快的得出结果
def isBalanced(self, root: TreeNode) -> bool:
    # 子底儿上
    def height(root):
        if not root:
            return 0
        leftHeight = height(root.left)
        if leftHeight == -1:
            return -1
        rightHeight = height(root.right)
        if rightHeight == -1:
            return -1
        if abs(leftHeight - rightHeight) > 1:
            return -1
        return max(leftHeight, rightHeight) + 1
    return height(root) >= 0